package leecode.递归dfs;

import java.util.Arrays;

/**
 * @author wangxi03 created on 2021/6/1 5:34 下午
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/coin-change/
 */
public class CoinChange {

    public static void main(String[] args) {
        CoinChange obj = new CoinChange();
        int[] nums = {1,2147483647};
        System.out.println(obj.coinChange(nums, 2));

        System.out.println((int)'z');
    }

    int min = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length <= 0) {
            return 0;
        }
        Arrays.sort(coins);
        help2(coins, amount, coins.length - 1, 0);
        if (min == Integer.MAX_VALUE) {
            return -1;
        }
        return min;
    }

    // 普通的深搜 会超时，直接单个数字走到底
    private void help1(int[] coins, int amount, int index, int count) {
        if (amount == 0) {
            min = Math.min(count, min);
            return;
        }
        if (amount < 0) {
            return;
        }
        for (int i = index; i >= 0; i--) {
            help1(coins, amount - coins[i], i, count + 1);
        }
    }


    // 这种深搜 oj 也过不去，，只能使用动态规划了
    private void help2(int[] coins, int amount, int index, int count) {
        if (amount == 0) {
            min = Math.min(count, min);
            return;
        }
        if (amount < 0) {
            return;
        }
        if (index < 0) {
            return;
        }
        // 计算出最大这个面额的硬币数，不用盲目的一直去搜这中硬币了
        int k = amount/coins[index];
        for (int i = k; i >= 0 && (count + i < min); i--) {
            help2(coins, amount - i * coins[index], index - 1, count + i);
        }
    }
}
